#include "../include/RedBlackAbstruct.h"
#include <cassert>

RedBlackNode* RedBlackAbstruct::createNode(int key, int value) const
{
	RedBlackNode* root = new RedBlackNode;

	root->color = Color::RED;

	root->key = key;

	root->value = value;

	root->left = root->right = root->parent = nullptr;

	return root;
}

RedBlackNode* RedBlackAbstruct::getGrandfather(RedBlackNode* node)
{
	if (!node || !node->parent)
	{
		return nullptr;
	}

	return node->parent->parent;
}

RedBlackNode* RedBlackAbstruct::getUncle(RedBlackNode* node)
{
	return this->siblings(node->parent);
}

RedBlackNode* RedBlackAbstruct::siblings(RedBlackNode* node)
{
	if (!node || !node->parent)
	{
		return nullptr;
	}
	if (node == node->parent->left)
	{
		return node->parent->right;
	}

	return node->parent->left;
}

void RedBlackAbstruct::insetCaseOne(RedBlackNode* node)
{
	// 如果父节点不为空 则不做处理
	if (node->parent)
	{
		this->insetCaseTwo(node);
		return;
	}

	node->color = Color::BLACK;
}

void RedBlackAbstruct::insetCaseTwo(RedBlackNode* node)
{
	if (Color::BLACK == this->getNodeColor(node->parent))
	{
		return;
	}

	this->insertCaseThree(node);
}

void RedBlackAbstruct::insertCaseThree(RedBlackNode* node)
{
	RedBlackNode* uncle = this->getUncle(node);

	if (Color::RED == this->getNodeColor(uncle))
	{
		node->parent->color = Color::BLACK;

		uncle->color = Color::BLACK;

		RedBlackNode* grandfather = this->getGrandfather(node);

		grandfather->color = Color::RED;

		this->insetCaseOne(grandfather);

		grandfather = nullptr;
	}
	else {
		this->insertCaseFoure(node);
	}
}

void RedBlackAbstruct::insertCaseFoure(RedBlackNode* node)
{
	if (node == node->parent->left && this->getGrandfather(node)->right == node->parent)
	{
		this->rotateRight(node->parent);

		node = node->right;
	}
	else if (node == node->parent->right && this->getGrandfather(node)->left == node->parent)
	{
		this->rotateLeft(node->parent);

		node = node->left;
	}

	this->insertCaseFive(node);
}

void RedBlackAbstruct::insertCaseFive(RedBlackNode* node)
{
	node->parent->color = Color::BLACK;

	RedBlackNode* grandFather = this->getGrandfather(node);

	grandFather->color = Color::RED;

	if (node == node->parent->left && node->parent == grandFather->left)
	{
		// 右旋
		this->rotateRight(grandFather);
	}
	else if (node == node->parent->right && node->parent == grandFather->right)
	{
		// 左旋
		this->rotateLeft(grandFather);
	}
}

Color RedBlackAbstruct::getNodeColor(RedBlackNode* node) const
{
	return node ? node->color : Color::BLACK;
}

void RedBlackAbstruct::rotateRight(RedBlackNode* node)
{
	RedBlackNode* left = node->left;

	this->replaceNode(node, left);

	node->left = left->right;

	if (nullptr != left->right) {

		left->right->parent = node;
	}

	left->right = node;

	node->parent = left;
}

void RedBlackAbstruct::rotateLeft(RedBlackNode* node)
{
	RedBlackNode* right = node->right;

	this->replaceNode(node, right);

	node->right = right->left;

	if (nullptr != right->left) {

		right->left->parent = node;
	}

	right->left = node;

	node->parent = right;
}

void RedBlackAbstruct::replaceNode(RedBlackNode* old, RedBlackNode* newNode)
{
	if (nullptr == old->parent)
	{
		this->root = newNode;
	}
	else if (old == old->parent->left)
	{
		old->parent->left = newNode;
	}
	else
	{
		old->parent->right = newNode;
	}

	if (nullptr != newNode)
	{
		newNode->parent = old->parent;
	}
}

RedBlackNode* RedBlackAbstruct::findTheLowestRightNode(RedBlackNode* node)
{
	// 保险起见
	assert(node != nullptr);

	while (node->right)
	{
		node = node->right;
	}

	return node;
}

void RedBlackAbstruct::deleteCaseOne(RedBlackNode* node)
{
	if (nullptr == node->parent)
	{
		return;
	}

	this->deleteCaseTwo(node);
}

void RedBlackAbstruct::deleteCaseTwo(RedBlackNode* node)
{
	RedBlackNode* sibling = this->siblings(node);

	if (Color::RED == this->getNodeColor(sibling))
	{
		node->parent->color = Color::RED;

		sibling->color = Color::BLACK;

		if (node == node->parent->right)
		{
			this->rotateRight(node->parent);
		}
		else
		{
			this->rotateLeft(node->parent);
		}
	}

	this->deleteCaseThree(node);

	sibling = nullptr;
}

void RedBlackAbstruct::deleteCaseThree(RedBlackNode* node)
{
	RedBlackNode* sibling = this->siblings(node);
	if (Color::BLACK == this->getNodeColor(node->parent)
		&& Color::BLACK == this->getNodeColor(sibling)
		&& Color::BLACK == this->getNodeColor(sibling->left)
		&& Color::BLACK == this->getNodeColor(sibling->right)
		)
	{
		sibling->color = Color::RED;

		this->deleteCaseOne(node->parent);
	}
	else
	{
		this->deleteCaseFour(node);
	}


	sibling = nullptr;
}

void RedBlackAbstruct::deleteCaseFour(RedBlackNode* node)
{
	RedBlackNode* sibling = this->siblings(node);
	if (Color::RED == this->getNodeColor(node->parent)
		&& Color::BLACK == this->getNodeColor(sibling)
		&& Color::BLACK == this->getNodeColor(sibling->left)
		&& Color::BLACK == this->getNodeColor(sibling->right)
		)
	{
		sibling->color = Color::RED;

		node->parent->color = Color::BLACK;
	}
	else
	{
		this->deleteCaseFive(node);
	}


	sibling = nullptr;
}

void RedBlackAbstruct::deleteCaseFive(RedBlackNode* node)
{

	RedBlackNode* sibling = this->siblings(node);

	//双空旋转
	if (node == node->parent->left &&
		Color::BLACK == this->getNodeColor(node)
		&& Color::RED == this->getNodeColor(sibling->left)
		&& Color::BLACK == this->getNodeColor(sibling->right)
		)
	{
		sibling->left->color = Color::BLACK;

		this->rotateRight(sibling);
	}
	else if (node == node->parent->right 
		&& Color::BLACK == this->getNodeColor(node)
		&& Color::RED == this->getNodeColor(sibling->right)
		&& Color::BLACK == this->getNodeColor(sibling->left))
	{
		sibling->right->color = Color::BLACK;
		this->rotateLeft(sibling);
	}
	this->deleteCaseSix(node);
}

void RedBlackAbstruct::deleteCaseSix(RedBlackNode* node)
{
	RedBlackNode* sibling = this->siblings(node);

	sibling->color = this->getNodeColor(node->parent);

	node->parent->color = Color::BLACK;

	if (node == node->parent->right)
	{
		sibling->left->color = Color::BLACK;

		this->rotateRight(node->parent);
	}
	else
	{
		sibling->right->color = Color::BLACK;

		this->rotateLeft(node->parent);
	}
}

void RedBlackAbstruct::clearByOnlyHaveOneNode()
{
	delete this->root;

	this->root = nullptr;
}

RedBlackAbstruct::RedBlackAbstruct(): root(nullptr)
{
}

RedBlackAbstruct::RedBlackAbstruct(int key, int value)
{
	this->root = this->createNode(key, value);

}

RedBlackNode* RedBlackAbstruct::getRoot() const
{
	return this->root;
}

void RedBlackAbstruct::setRoot(RedBlackNode* node)
{
	this->root = node;
}

RedBlackNode* RedBlackAbstruct::findNode(int key)
{
	RedBlackNode* root = this->root;

	while (nullptr != root)
	{
		if (key < root->key)
		{
			root = root->left;
		}
		else if (key > root->key) {
			root = root->right;
		}
		else {
			return root;
		}
	}

	return nullptr;
}


